#include <stdio.h>
#include <stdlib.h>

#define MAX 10
typedef char DataType;

typedef struct node {
    DataType data;
    struct node *left, *right;
    // 1 存放线索 0存放节点
    int ltag, rtag;
} BinThrTree;

// 栈
typedef struct {
    BinThrTree *list[MAX];
    int top;
} Stack;

int isEmpty(Stack *stack) {
    return stack->top == -1;
}

int isFull(Stack *stack) {
    return stack->top == MAX - 1;
}

void push(Stack *stack, BinThrTree *value) {

    if (isFull(stack)) {
        printf("stack is full! top={%d}\n", stack->top);
        return;
    }
    stack->list[++stack->top] = value;
}

/**
 * 获取栈顶元素，但是不退栈
 * @return
 */
BinThrTree *get(Stack *stack) {

    if (isEmpty(stack)) {
        printf("stack is empty!\n");
        return NULL;
    }
    return stack->list[stack->top];
}


BinThrTree *pop(Stack *stack) {
    if (isEmpty(stack)) {
        printf("stack is empty!\n");
        return NULL;
    }
    return stack->list[stack->top--];
}

Stack *initStack() {

    Stack *stack = (Stack *) malloc(sizeof(Stack));
    stack->top = -1;

    return stack;
}


BinThrTree *init() {

    DataType ch;

    // 头元素
    BinThrTree *top = NULL;
    // 新元素
    BinThrTree *item = NULL;

    int k;

    Stack *stack = initStack();

    while ((ch = getchar()) != '\n') {

        switch (ch) {

            case '(':
                push(stack, top);
                k = 1;
                break;
            case ',':
                k = 2;
                break;
            case ')':
                top = pop(stack);
                break;
            default:
                item = (BinThrTree *) malloc(sizeof(BinThrTree));
                item->data = ch;
                item->left = NULL;
                item->right = NULL;
                item->ltag = 0;
                item->rtag = 0;

                top = item;

                BinThrTree *d = get(stack);

                if (d != NULL) {
                    if (k == 1) {
                        // 操作左侧
                        d->left = item;
                    } else {
                        // 操作右侧
                        d->right = item;
                    }
                }
                break;
        }
    }
    return top;
}

// 先序线索化
void cover(BinThrTree *item) {

    // 用一个静态保存
    static BinThrTree *top = NULL;

    // 操作当前节点
    if (item == NULL) {
        return;
    }

    if (item->left == NULL) {
        // 设置线索
        item->ltag = 1;
    }

    if (item->right == NULL) {
        item->rtag = 1;
    }

    // 给前节点添加右线索
    if (top != NULL && top->rtag == 1) {
        top->right = item;
    }
    // 给当前节点添加前线索
    if (item->ltag == 1) {
        item->left = top;
    }

    top = item;

    if (item->ltag == 0) {
        cover(item->left);
    }
    if (item->rtag == 0) {
        cover(item->right);
    }

}

void printNode(BinThrTree *tree) {

    if (tree->ltag == 1) {
        printf("ltag=%c,", tree->left == NULL ? '0' : tree->left->data);
    } else {
        printf("ltag=%p,", tree->left);
    }

    printf("data=%c,", tree->data);

    if (tree->rtag == 1) {
        printf("rtag=%c", tree->right == NULL ? '0' : tree->right->data);
    } else {
        printf("rtag=%p", tree->right);
    }

    printf("\n");

}

// 先序遍历
void first(BinThrTree *tree) {
    if (NULL == tree) {
        return;
    }

    printNode(tree);

    if (tree->ltag == 0) {
        first(tree->left);
    }
    if (tree->rtag == 0) {
        first(tree->right);
    }

}

BinThrTree *nextNode(BinThrTree *binThrTree) {

    BinThrTree *item = binThrTree;

    // 当前节点的下一个节点
    if (binThrTree->rtag == 1) {
        return binThrTree->right;
    } else {
        // 当前节点有下一个节点
        item = binThrTree->left;

        return item;
    }
}

// 这里是先序，所以直接从首节点开始
void forEach(BinThrTree *binThrTree) {
    BinThrTree *top = binThrTree;
    while (top != NULL) {
        printf("%c,", top->data);
        top = nextNode(top);
    }
}

int main() {
    printf("bin tre tree: A(B(D,E),C) \n");

    BinThrTree *binThrTree = init();
    // 进行线索化
    first(binThrTree);

    // 进行转换
    printf("loading...cover \n");
    cover(binThrTree);
    first(binThrTree);

    printf("\n");
    BinThrTree *next = nextNode(binThrTree->right);
    printf("next node %p\n", next);

    forEach(binThrTree);

    return 0;
}
